package lt115

/*lt115   dp
剑指 Offer II 097. 子序列的数目
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）
字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

2: 怎么想到这样状态方程的？

一点个人经验，见过的很多2个串的题，大部分都是dp[i][j] 分别表示s串[0...i] 和t串[0...j]怎么怎么样
然后都是观察s[i]和t[j]分等或者不等的情况
	而且方程通常就是 dp[i-1][j-1] 要么+ 要么 || dp[i-1][j]类似的
类似的题比如有 10：正则表达式匹配 44：通配符匹配 编辑距离 1143：最长公共子序列等等的 还有几道想不起来了
*/
/*
dp[i][j] : s[i:]  t[j:]   表示在 s[i:]s[i:] 的子序列中 t[j:]t[j:] 出现的个数。
从后往前
当 j=n 时，t[j:] 为空字符串，由于空字符串是任何字符串的子序列，
	因此对任意0≤i≤m，有 dp[i][n]=1；
当 i=m 且 j<n 时，s[i:] 为空字符串，t[j:] 为非空字符串，由于非空字符串不是空字符串的子序列，
	因此对任意 0≤j<n，有 dp[m][j]=0。


*/
func numDistinct(s string, t string) int {
	m,n := len(s),len(t)
	if m<n{
		return 0
	}
	dp := make([][]int,m+1)
	for i:=range dp{
		dp[i] = make([]int, n+1)
		dp[i][n]= 1   //t 为空串  dp[0][i] s为空城
	}

	for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if s[i] == t[j] { //进行匹配  考虑t[j+1:] 作为s[i+1:]的子序列   不进行匹配t[j:]作为s[j+1:]子序列
                dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
            } else {
                dp[i][j] = dp[i+1][j]
            }
        }
    }
    return dp[0][0]


}
